import java.util.*;

/**
 * 项目名称：wangxu
 * 类 名 称：hw1081
 * 描 述：
 * 创建时间：2023/1/20 9:49 上午
 * 创 建 人：wang-xu
 */
public class hw1081 {
    public static void main(String[] args) {
        String s = "cbacdcbc";
        Solution.smallestSubsequence(s);
    }
}

class Solution {
    public static String smallestSubsequence(String s) {
        // 单调栈
        Stack<Character> stack = new Stack<>();
        char[] ch = s.toCharArray();
        // 记录每个元素最后出现的下标
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndex[ch[i]-'a'] = i;
        }

        // 记录每个元素是否都在栈中出现
        boolean[] inStack = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            // 判断元素是否出现过
            if (inStack[ch[i] - 'a']) {
                continue;
            }
            // 1.栈非空 2.栈顶元素小于主元素 3.
            while (!stack.isEmpty() && stack.peek() > s.charAt(i) && lastIndex[stack.peek()-'a'] > i){
                // 移除栈中元素，需要将inStack对应元素赋值false
                inStack[stack.pop()-'a'] = false;
            }
            stack.push(s.charAt(i));
            inStack[ch[i]-'a'] = true;
        }

        // 遍历stack倒序取出数据
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            for (int m = 0;m <stack.size();m++){
                sb.append(stack.pop());
            }
        }
        return sb.reverse().toString();
    }

}
